//
// Created by Administrator on 2021/4/8.
//

/*
序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

提示: 输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。


示例 1：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

示例 2：
输入：root = []
输出：[]

示例 3：
输入：root = [1]
输出：[1]

示例 4：
输入：root = [1,2]
输出：[1,2]

提示：

树中结点数在范围 [0, 104] 内
-1000 <= Node.val <= 1000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。*/
#include <string>
#include <iostream>
#include <queue>

using namespace std;

// Definition for a binary tree node.
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;

    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}

    TreeNode(int x, TreeNode *l, TreeNode *r) : val(x), left(l), right(r) {}
};

void preorder(TreeNode *root, vector<int> &res) {
    if (root == nullptr) {
        return;
    }
    res.push_back(root->val);
    preorder(root->left, res); // 对左子节点递归调用
    preorder(root->right, res); // 对右子节点递归调用
}

vector<int> preorderTraversal(TreeNode *root) {
    vector<int> res; // 结果向量
    preorder(root, res);
    return res;
}
class Codec {
private:
    // 字符串储存序列化的结果
    string str;
    // 构建一个队列 储存节点数据
    queue<string> Q;
public:
    // 深度优先遍历 将树变为序列  前序遍历
    void doSerialization(TreeNode *root) {
        // 遇到空节点，加入none，
        if (root == nullptr) {
            str += "none,";
        } else {
            // 遇到非空节点，加入节点值及，
            str += to_string(root->val) + ",";
            doSerialization(root->left);
            doSerialization(root->right);
        }
    }

    // Encodes a tree to a single string.
    // 序列化
    // 遍历？
    string serialize(TreeNode *root) {
        doSerialization(root);
        return str;
    }

    TreeNode *doDeserialization() {
        string cur = Q.front();
        Q.pop();
        if (cur == "none") // 碰到none，说明是空节点
            return nullptr;
        auto *root = new TreeNode(stoi(cur)); // string to integer
        root->left = doDeserialization(); // 递归调用 构建左子节点
        root->right = doDeserialization(); // 构建右子节点
        return root;
    }

    // Decodes your encoded data to tree.
    // 将序列化的树重建回来
    TreeNode *deserialize(string data) {
        int i = 0, j = 0;
        // 按照','分割，把序列字符串变成队列
        while (i < data.size()) {
            if (data[i] != ',')
                i++;
            else {
                string tmp = data.substr(j, i - j); // 从j开始，i-j个字符
                Q.push(tmp); // 入队
                i++; // 指针移动
                j = i;
            }
        }
        if (j != i) {
            string tmp = data.substr(j, i - j);
            Q.push(tmp);
        }
        return doDeserialization();
    }


};

class Codec2 {  // 题解 括号表示编码 + 递归下降解码
public:
    string serialize(TreeNode *root) {
        if (!root) return "X";
        auto l = "(" + serialize(root->left) + ")";
        auto r = "(" + serialize(root->right) + ")";
        return l + to_string(root->val) + r;
    }

    inline TreeNode *parseSubtree(const string &data, int &ptr) {
        ++ptr; // 跳过左括号
        auto subtree = parse(data, ptr);
        ++ptr; // 跳过右括号
        return subtree;
    }

    // 取出数字
    inline int parseInt(const string &data, int &ptr) {
        int x = 0, sgn = 1;
        if (!isdigit(data[ptr])) {
            sgn = -1;
            ++ptr;
        }
        while (isdigit(data[ptr])) {
            x = x * 10 + data[ptr++] - '0';
        }
        return x * sgn;
    }

    // 建立节点
    TreeNode *parse(const string &data, int &ptr) {
        if (data[ptr] == 'X') {
            ++ptr;
            return nullptr;
        }
        auto cur = new TreeNode(0);
        cur->left = parseSubtree(data, ptr);
        cur->val = parseInt(data, ptr);
        cur->right = parseSubtree(data, ptr);
        return cur;
    }

    // 反序列化 入口
    TreeNode *deserialize(const string &data) {
        int ptr = 0;
        return parse(data, ptr);
    }
};

class Codec3 { // 优秀解答 bfs
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode *root) {
        if (root == nullptr)
            return "";
        string res_str;
        queue<TreeNode *> Q;
        Q.push(root);
        while (!Q.empty()) {
            TreeNode *p = Q.front();
            Q.pop();
            if (p == nullptr) {
                res_str += "NULL,";
            } else {
                // 层次遍历加入节点数据
                res_str += (to_string(p->val) + ',');
                Q.push(p->left);
                Q.push(p->right);
            }
        }
        return res_str;
    }

    // Decodes your encoded data to tree.
    TreeNode *deserialize(string data) {
        if (data.empty())
            return nullptr;
        vector<string> rec; // vector储存节点数据
        int i = 0, j = 0;
        while (i < data.size()) {
            if (data[i] != ',')
                i++;
            else {
                string tmp = data.substr(j, i - j);
                rec.push_back(tmp);
                i++;
                j = i;
            }
        }
        if (j != i) {
            string tmp = data.substr(j, i - j);
            rec.push_back(tmp);
        }
        auto *root = new TreeNode(stoi(rec[0]));
        queue<TreeNode *> Q;
        Q.push(root);
        i = 1;
        while (!Q.empty()) {
            TreeNode *p = Q.front();
            Q.pop();
            if (rec[i] != "NULL") {
                p->left = new TreeNode(stoi(rec[i]));
                Q.push(p->left);
            }
            i++;
            if (rec[i] != "NULL") {
                p->right = new TreeNode(stoi(rec[i]));
                Q.push(p->right);
            }
            i++;
        }
        return root;
    }
};

// Your Codec object will be instantiated and called as such:
// Codec ser, deser;
// TreeNode* ans = deser.deserialize(ser.serialize(root));

int main() {
    auto t5 = TreeNode(5);
    auto t4 = TreeNode(4);
    auto t3 = TreeNode(3, &t4, &t5);
    auto t2 = TreeNode(2);
    auto t1 = TreeNode(1, &t2, &t3);
    Codec ser, deser;
    TreeNode *ans = deser.deserialize(ser.serialize(&t1));
    vector<int> s = preorderTraversal(ans);
    for (auto x:s) cout << x << endl;
    return 0;
}